package exercises.leetcode;

import exercises.leetcode.utils.Node;

/**
 * <a href="https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof">
 * 剑指 Offer 35. 复杂链表的复制</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
 * <p>
 * 示例 1：
 * <p>
 * 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
 * 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
 * 示例 2：
 * <p>
 * 输入：head = [[1,1],[2,1]]
 * 输出：[[1,1],[2,1]]
 * 示例 3：
 * <p>
 * 输入：head = [[3,null],[3,0],[3,null]]
 * 输出：[[3,null],[3,0],[3,null]]
 * 示例 4：
 * <p>
 * 输入：head = []
 * 输出：[]
 * 解释：给定的链表为空（空指针），因此返回 null。
 *  
 * <p>
 * 提示：
 * <p>
 * -10000 <= Node.val <= 10000
 * Node.random 为空（null）或指向链表中的节点。
 * 节点数目不超过 1000 。
 *  
 * <p>
 * 注意：本题与主站 138 题相同：https://leetcode-cn.com/problems/copy-list-with-random-pointer/
 * <p>
 *  
 *
 * @author or2
 * @date 2021年09月21日 时间: 18:25
 */
public class Offer35 {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }

        Node p = head;
        /*第一遍, 复制链表*/
        while (p != null) {
            Node newNode = new Node(p.val);
            newNode.next = p.next;
            p.next = newNode;
            newNode.random = p.random;
            p = p.next.next;
        }

        p = head;
        /*第二遍, 重新赋值random*/
        while (p != null) {
            if (p.random != null) {
                p.next.random = p.random.next;
            }
            p = p.next.next;
        }

        p = head;
        Node q = p.next;
        Node ans = q;
        /*分开链表*/
        while (true) {
            p.next = p.next.next;
            if (p.next == null) {
                break;
            }
            q.next = p.next.next;
            p = p.next;
            q = q.next;
        }

        return q;
    }
}
